//
// Created by wushuo on 2021/1/16.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class BinaryIndexTree {
    vector<int> bit;
    vector<int> *num;
    int size;

    static int lowBit(int x) {
        return x & (-x);
    }

public:
    void build(vector<int>& nums) {
        num = &nums;
        size = nums.size();
        bit = vector<int>(size + 1, 0);
        for (int i = 0; i < size; i++) {
            update(i, nums[i]);
        }
    }

    void buildBit(vector<int>& nums) {
        size = nums.size();
        bit = vector<int>(size + 1, 0);
    }

    int sum(int k) {
        k++;
        int res = 0;
        // n - lowBit(n) 代表什么呢？代表的是 n 节点的左祖父/父节点
        for (int i = k; i > 0; i -= lowBit(i)) {
            res += bit[i];
        }
        return res;
    }

    // 从 BIT 的定义可知，A[k] 的值会影响 k 的所有右祖父/父节点
    void update(int k, int delta) {
        k++;
        for (int i = k; i <= size; i += lowBit(i)) {
            bit[i] += delta;
        }
    }
};

class Solution {
public:

    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<int> sums;
        int cur = 0;
        for (int num: nums) {
            cur += num;
            sums.push_back(cur);
        }
        int n = sums.size();

        // 同理，这几行也没有用，其实只使用带了sum和update功能
        BinaryIndexTree bit;
        vector<int> tree(n);
        bit.buildBit(tree);

        int ans = 0;

        vector<int> copy(sums);

        std::sort(copy.begin(), copy.end());
        // 这个算法不在受限于nums的范围，通过一层转换使得bit的树状数组size为n + 1
        // 考虑下之前，我们直接更新bit[nums[i]]，然后计算0 ~ nums[i] - 1 的和，就是已经出现过的小于nums[i]的数目
        // 但是其实还可以更简单，我们更新排序数组的bit[index]，0 ~ index - 1的和也是已经出现过的小于nums[i]的数目
        // 下面举一个例子来说明：5, 3, 6, 1, 0, 3, 5, 2, 5, 1
        // 排序后 0, 1, 1, 2, 3 ,3, 5, 5, 5, 6
        // 以下为了方便，bit的数组index是从0开始的，实际上0是没用的
        // 第二个搜索5，index为6, 由于之前已经更新了bit[1] = 1, 所以结果为1
        // 搜索2，index为3, 之前已经更新了bit[1] = 1, bit[6] = 1, 结果为1
        // 搜索3，index为4, 之前已经更新了bit[1] = 1, bit[6] = 1, 结果为1
        // 搜索6，index为9, 之前已经更新了bit[0] = 1, bit[1] = 2, bit[3] = 1, bit[4] = 1, bit[6] = 2, 结果为7
        for (int i = n - 1; i >= 0; i--) {
            int num = sums[i];
            int index = std::lower_bound(copy.begin(), copy.end(), num) - copy.begin();
            ans += bit.sum(index + upper) - bit.sum(index + lower - 1);
            bit.update(index, 1);
        }

        return ans;
    }
};